/**
 * @a https://leetcode.cn/problems/powx-n/description/
 */

#include "../common.h"

class Solution {
public:
    double myPow(double x, int n) {
        long long N = n; // 避免溢出
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
        return quick_pow(x,n);
    }
    double quick_pow(double x, int n){
        if(n == 0) return 1.0;
        double half = quick_pow(x * x, n / 2);
        return (n % 2 == 0) ? half : half * x;
    }
};